home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / network / mail / pathalia.zoo / src / mapit.c < prev    next >
C/C++ Source or Header  |  1991-01-12  |  16KB  |  680 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapit.c    9.13 88/06/12";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. #define chkheap(i)    /* void */
  9. #define chkgap()    /* int */
  10.  
  11. #define trprint(stream, n) \
  12.     fprintf((stream), (n)->n_flag & NTERMINAL ? "<%s>" : "%s", (n)->n_name)
  13.  
  14. /* exports */
  15. /* invariant while mapping: Nheap < Hashpart */
  16. long Hashpart;        /* start of unreached nodes */
  17. long Nheap;        /* end of heap */
  18. long NumNcopy, Nlink, NumLcopy;
  19.  
  20. void mapit();
  21.  
  22. /* imports */
  23. extern long Nheap, Hashpart, Tabsize, Tcount;
  24. extern int Tflag, Vflag;
  25. extern node **Table, *Home;
  26. extern char *Linkout, *Graphout;
  27.  
  28. extern void freelink(), resetnodes(), printit(), dumpgraph();
  29. extern void showlinks(), die();
  30. extern long pack(), allocation();
  31. extern link *newlink(), *addlink();
  32. extern int maptrace(), tiebreaker();
  33. extern node *ncopy();
  34.  
  35.  
  36. /* privates */
  37. static long    Heaphighwater;
  38. static link    **Heap;
  39.  
  40. STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
  41. STATIC void setheapbits(), mtracereport(), heapchildren(), otracereport();
  42. STATIC link *min_node();
  43. STATIC int dehash(), skiplink(), skipterminalalias();
  44. STATIC Cost costof();
  45. STATIC node *mappedcopy();
  46.  
  47. /* transform the graph to a shortest-path tree by marking tree edges */
  48. void
  49. mapit()
  50. {    register node *n;
  51.     register link *l;
  52.  
  53.     vprintf(stderr, "*** mapping\ttcount = %ld\n", Tcount);
  54.     Tflag = Tflag && Vflag;        /* tracing here only if verbose */
  55.     /* re-use the hash table space for the heap */
  56.     Heap = (link **) Table;
  57.     Hashpart = pack(0L, Tabsize - 1);
  58.  
  59.     /* expunge penalties from -a option and make circular copy lists */
  60.     resetnodes();
  61.  
  62.     if (Linkout && *Linkout)    /* dump cheapest links */
  63.         showlinks();
  64.     if (Graphout && *Graphout)    /* dump the edge list */
  65.         dumpgraph();
  66.  
  67.     /* insert Home to get things started */
  68.     l = newlink();        /* link to get things started */
  69.     l->l_to = Home;
  70.     (void) dehash(Home);
  71.     insert(l);
  72.  
  73.     /* main mapping loop */
  74.     do {
  75.         Heaphighwater = Nheap;
  76.         while ((l = min_node()) != 0) {
  77.             l->l_flag |= LTREE;
  78.             n = l->l_to;
  79.             if (n->n_flag & MAPPED)        /* sanity check */
  80.                 die("mapped node in heap");
  81.             if (Tflag && maptrace(n, n))
  82.                 otracereport(n);    /* tracing */
  83.             chkheap(1); chkgap();        /* debugging */
  84.             n->n_flag |= MAPPED;
  85.             heapchildren(n);    /* add children to heap */
  86.         }
  87.         vprintf(stderr, "heap hiwat %d\nalloc %ldk, ncopy = %ld, nlink = %ld, lcopy = %ld\n", Heaphighwater, allocation(), NumNcopy, Nlink, NumLcopy);
  88.  
  89.         if (Nheap != 0)        /* sanity check */
  90.             die("null entry in heap");
  91.  
  92.         /*
  93.          * add back links from unreachable hosts to reachable
  94.          * neighbors, then remap.  asymptotically, this is
  95.          * quadratic; in practice, this is done once or twice,
  96.          * when n is small.
  97.          */
  98.         backlinks();
  99.     } while (Nheap > 0);
  100.  
  101.     if (Hashpart < Tabsize) {
  102.         int foundone = 0;
  103.  
  104.         for ( ; Hashpart < Tabsize; Hashpart++) {
  105.             if (Table[Hashpart]->n_flag & ISPRIVATE)
  106.                 continue;
  107.             if (foundone++ == 0)
  108.                 fputs("You can't get there from here:\n", stderr);
  109.             putc('\t', stderr);
  110.             trprint(stderr, Table[Hashpart]);
  111.             putc('\n', stderr);
  112.         }
  113.     }
  114. }
  115.  
  116. STATIC void
  117. heapchildren(n)
  118.     register node *n;
  119. {    register link *l;
  120.     register node *next;
  121.     register int mtrace;
  122.     register Cost cost;
  123.  
  124.     for (l = n->n_link; l; l = l->l_next) {
  125.  
  126.         next = l->l_to;        /* neighboring node */
  127.         mtrace = Tflag && maptrace(n, next);
  128.  
  129.         if (l->l_flag & LTREE)
  130.             continue;
  131.  
  132.         if (l->l_flag & LTERMINAL)
  133.             l->l_to = next = ncopy(n, l);
  134.  
  135.         if ((n->n_flag & NTERMINAL) && (l->l_flag & LALIAS))
  136.             if (skipterminalalias(n, next))
  137.                 continue;
  138.             else
  139.                 l->l_to = next = ncopy(n, l);
  140.  
  141.         if (next->n_flag & MAPPED) {
  142.             if (mtrace)
  143.                 mtracereport(n, l, "-\talready mapped");
  144.             continue;
  145.         }
  146.         cost = costof(n, l);
  147.  
  148.         if (skiplink(l, n, cost, mtrace))
  149.             continue;
  150.  
  151.         /*
  152.          * put this link in the heap and restore the
  153.          * heap property.
  154.          */
  155.         if (mtrace) {
  156.             if (next->n_parent)
  157.                 mtracereport(next->n_parent, l, "*\tdrop");
  158.             mtracereport(n, l, "+\tadd");
  159.         }
  160.         next->n_parent = n;
  161.         if (dehash(next) == 0) {  /* first time */
  162.             next->n_cost = cost;
  163.             insert(l);      /* insert at end */
  164.             heapup(l);
  165.         } else {
  166.             /* replace inferior path */
  167.             Heap[next->n_tloc] = l;
  168.             if (cost > next->n_cost) {
  169.                 /* increase cost (gateway) */
  170.                 next->n_cost = cost;
  171.                 heapdown(l);
  172.             } else if (cost < next->n_cost) {
  173.                 /* cheaper route */
  174.                 next->n_cost = cost;
  175.  
  176.                 heapup(l);
  177.             }
  178.         }
  179.         setheapbits(l);
  180.         chkheap(1);
  181.  
  182.     }
  183. }
  184.  
  185. /* 
  186.  * bizarro special case.  this merits comment.
  187.  * 
  188.  * n is a terminal node just sucked out of the heap, next is an alias
  189.  * for n.  because n is terminal, it must have one or more "copies."
  190.  * if next is one of those copies, don't put next in the heap.
  191.  *
  192.  * does that clear things up?
  193.  */
  194. STATIC int
  195. skipterminalalias(n, next)
  196.     node *n, *next;
  197. {
  198.  
  199.     while (n->n_flag & NALIAS) {
  200.         n = n->n_parent;
  201.         if (ALTEREGO(n, next))
  202.             return 1;
  203.     }
  204.     return 0;
  205. }
  206.  
  207. /*
  208.  * return 1 if we definitely don't want want this link in the
  209.  * shortest path tree, 0 if we might want it, i.e., best so far.
  210.  *
  211.  * if tracing is turned on, report only if this node is being skipped.
  212.  */
  213. STATIC int
  214. skiplink(l, parent, cost, trace)
  215.     link *l;        /* new link to this node */
  216.     node *parent;        /* (potential) new parent of this node */
  217.     register Cost cost;    /* new cost to this node */
  218.     int trace;        /* trace this link? */
  219. {    register node *n;    /* this node */
  220.     register link *lheap;        /* old link to this node */
  221.  
  222.     n = l->l_to;
  223.  
  224.     /* first time we've reached this node? */
  225.     if (n->n_tloc >= Hashpart)
  226.         return 0;
  227.  
  228.     lheap = Heap[n->n_tloc];
  229.  
  230.     /* examine links to nets that require gateways */
  231.     if (GATEWAYED(n)) {
  232.         /* if exactly one is a gateway, use it */
  233.         if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
  234.             if (trace)
  235.                 mtracereport(parent, l, "-\told gateway");
  236.             return 1;    /* old is gateway */
  237.         }
  238.         if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
  239.             return 0;    /* new is gateway */
  240.  
  241.         /* no gateway or both gateways;  resolve in standard way ... */
  242.     }
  243.  
  244.     /* examine dup link (sanity check) */
  245.     if (n->n_parent == parent && (DEADLINK(lheap) || DEADLINK(l)))
  246.         die("dup dead link");
  247.  
  248.     /*  examine cost */
  249.     if (cost < n->n_cost)
  250.         return 0;
  251.     if (cost > n->n_cost) {
  252.         if (trace)
  253.             mtracereport(parent, l, "-\tcheaper");
  254.         return 1;
  255.     }
  256.  
  257.     /* all other things being equal, ask the oracle */
  258.     if (tiebreaker(n, parent)) {
  259.         if (trace)
  260.             mtracereport(parent, l, "-\ttiebreaker");
  261.         return 1;
  262.     }
  263.     return 0;
  264. }
  265.  
  266. /* compute cost to l->l_to via parent */
  267. STATIC Cost
  268. costof(prev, l)
  269.     register node *prev;
  270.     register link *l;
  271. {    register node *next;
  272.     register Cost cost;
  273.  
  274.     if (l->l_flag & LALIAS)
  275.         return prev->n_cost;    /* by definition */
  276.  
  277.     next = l->l_to;
  278.     cost = prev->n_cost + l->l_cost;    /* basic cost */
  279.  
  280.     /*
  281.      * heuristics:
  282.      *    charge for a dead link.
  283.      *    charge for getting past a terminal host
  284.      *        or getting out of a dead host.
  285.      *    charge for getting into a gatewayed net (except at a gateway).
  286.      *    discourage mixing of syntax (when prev is a host).
  287.      *
  288.      * life was simpler when pathalias computed true shortest paths.
  289.      */
  290.     if (DEADLINK(l))
  291.         cost += INF;                /* dead link */
  292.     if (DEADHOST(prev))
  293.         cost += INF;                /* dead parent */
  294.     if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))
  295.         cost += INF;                /* not gateway */
  296.     if (!ISANET(prev)) {
  297.         if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
  298.          || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
  299.             cost += INF;            /* mixed syntax */
  300.     }
  301.  
  302.     return cost;
  303. }
  304.  
  305. /* binary heap implementation of priority queue */
  306.  
  307. STATIC void
  308. insert(l)
  309.     link *l;
  310. {    register node *n;
  311.  
  312.     n = l->l_to;
  313.     if (n->n_flag & MAPPED)
  314.         die("insert mapped node");
  315.  
  316.     Heap[n->n_tloc] = 0;
  317.     if (Heap[Nheap+1] != 0)
  318.         die("heap error in insert");
  319.     if (Nheap++ == 0) {
  320.         Heap[1] = l;
  321.         n->n_tloc = 1;
  322.         return;
  323.     }
  324.     if (Vflag && Nheap > Heaphighwater)
  325.         Heaphighwater = Nheap;    /* diagnostics */
  326.  
  327.     /* insert at the end.  caller must heapup(l). */
  328.     Heap[Nheap] = l;
  329.     n->n_tloc = Nheap;
  330. }
  331.  
  332. /*
  333.  * "percolate" up the heap by exchanging with the parent.  as in
  334.  * min_node(), give tiebreaker() a chance to produce better, stable
  335.  * routes by moving nets and domains close to the root, nets closer
  336.  * than domains.
  337.  *
  338.  * i know t